package com.colter.project.data.structure.sort;

public class InsertionSort {

	public static int[] sort(int[] arr) {
		int[] result = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			int position = 0;
			if (i != 0) {
				position = findPosition(result, 0, i - 1, arr[i]);
			}

			for (int j = i; j > position; j--) {
				result[j] = result[j - 1];
			}
			result[position] = arr[i];
		}

		return result;
	}

	public static int findPosition(int[] sub, int start, int end, int value) {
		int position = 0;
		if (value > sub[end]) {
			position = end + 1;
		} else if (value < sub[start]) {
			position = start;
		} else {
			int middle = (start + end) / 2;
			if (value > sub[middle]) {
				position = findPosition(sub, middle + 1, end, value);
			} else if (value < sub[middle]) {
				position = findPosition(sub, start, middle, value);
			} else {
				position = middle;
			}
		}
		return position;
	}

}
